package algorithm.leetcode.I101to200;

import java.util.*;

public class Q120 {

    public int minimumTotal(List<List<Integer>> triangle) {
        int minRouteSum = Integer.MAX_VALUE;

        int[] dp = new int[triangle.size()];

        if (triangle.size() == 0 || triangle.get(0).size() == 0) return 0;
        dp[0] = triangle.get(0).get(0);

        for (int i = 1; i < triangle.size(); i++) {
            int[] helper = dp.clone();
            for (int j = 0; j < triangle.get(i).size(); j++) {
                int before = Math.max(j - 1, 0);
                int after = Math.min(j, triangle.get(i-1).size());

                if (j == 0) dp[j] = triangle.get(i).get(0) + helper[0];  // 最左边单独讨论
                else if (j == triangle.get(i).size() - 1) dp[j] = triangle.get(i).get(j) + helper[j-1];  // 最右边单独讨论
                else dp[j] = triangle.get(i).get(j) + Math.min(helper[before], helper[after]);
            }
        }

        for (int i : dp) {
            minRouteSum = Math.min(minRouteSum, i);
        }
        return minRouteSum;
    }

    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>(Arrays.asList(-7));
        List<Integer> b = new ArrayList<>(Arrays.asList(-2,1));
        List<Integer> c = new ArrayList<>(Arrays.asList(-5,-5,9));
        List<Integer> d = new ArrayList<>(Arrays.asList(-4,-5,4,4));
        List<Integer> e = new ArrayList<>(Arrays.asList(-6,-6,2,-1,-5));
        List<Integer> f = new ArrayList<>(Arrays.asList(3,7,8,-3,7,-9));
        List<Integer> g = new ArrayList<>(Arrays.asList(-9,-1,-9,6,9,0,7));
        List<Integer> h = new ArrayList<>(Arrays.asList(-7,0,-6,-8,7,1,-4,9));
        List<Integer> i = new ArrayList<>(Arrays.asList(-3,2,-6,-9,-7,-6,-9,4,0));
        List<Integer> j = new ArrayList<>(Arrays.asList(-8,-6,-3,-9,-2,-6,7,-5,0,7));
        List<Integer> k = new ArrayList<>(Arrays.asList(-9,-1,-2,4,-2,4,4,-1,2,-5,5));
        List<Integer> l = new ArrayList<>(Arrays.asList(1,1,-6,1,-2,-4,4,-2,6,-6,0,6));
        List<Integer> m = new ArrayList<>(Arrays.asList(-3,-3,-6,-2,-6,-2,7,-9,-5,-7,-5,5,1));

        List<List<Integer>> aa = new ArrayList<>();
        aa.add(a);
        aa.add(b);
        aa.add(c);
        aa.add(d);
        aa.add(e);
        aa.add(f);
        aa.add(g);
        aa.add(h);
        aa.add(i);
        aa.add(j);
        aa.add(k);
        aa.add(l);
        aa.add(m);

        Q120 q120 = new Q120();
        System.out.println(q120.minimumTotal(aa));

    }

}
